package ai.zixing.mashibing.basic_class.class05;

public class Code04_RadixSort {

    public static void radixSort(int[] arr) {
        if (arr == null && arr.length < 2) {
            return;
        }
        radixSort(arr, 0, arr.length - 1, maxbits(arr));
    }

    // 获取 arr 上最大数的位数
    public static int maxbits(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int ar : arr) {
            max = Math.max(max, ar);
        }
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }

    // arr[L, R] 上排序
    // arr 上最大数的位数
    public static void radixSort(int[] arr, int L, int R, int digit) {
        // 十进制有 0-9 十个数
        final int radix = 10;
        int i = 0;
        int j = 0;
        // 有多少个数准备多少个辅助空间
        int[] help = new int[R - L + 1];
        // 最大数有多少位就进出多少次
        for (int d = 1; d <= digit; d++) {
            // 10个空间
            int[] count = new int[radix];
            // 从左往右看
            for (i = L; i <= R; i++) {
                j = getDigit(arr[i], d);
                count[j]++;
            }
            // 将 count 重写为前缀和
            // 表示 当前位数小于 i 的有几个
            // count[0] 当前位(d位)是0的数字有多少个
            // count[1] 当前位(d位)是(0和1)的数字有多少个
            // count[2] 当前位(d位)是(0、1和2)的数字有多少个
            // count[i] 当前位(d位)是(0~i)的数字有多少个
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }
            // 从右往左看
            for (i = R; i >= L; i--) {
                j = getDigit(arr[i], d);
                // 从右往左看每次都是最后一个出来的数【队列结构中】
                help[count[j] - 1] = arr[i];
                // 取出一个数据后，count数量减一
                count[j]--;
            }
            for (i = L, j = 0; i <= R; i++, j++) {
                arr[i] = help[j];
            }
        }
    }

    public static int getDigit(int x, int d) {
        return x / ((int) Math.pow(10, d - 1)) % 10;
    }
}
